Negative-Free and Weight-Decorrelated Contrastive Network for Graph-Agnostic Clustering
BAI Shengxing1,2, ZHANG Yuhong1,2, ZHOU Peng3, WU Xindong1,2
1. Key Laboratory of Knowledge Engineering with Big Data of Ministry of Education, Hefei University of Technology, Hefei 230009; 2. School of Computer Science and Information Engineering, He-fei University of Technology, Hefei 230009; 3. School of Computer Science and Technology, Anhui University, Hefei 230601
Abstract：Existing contrastive deep graph clustering methods heavily rely on the homophily assumption of the input graph, and thereby result in false negatives in negative sampling and feature redundancy in heterophilous graphs. These problems degrade clustering performance. To solve these problems, a graph-agnostic clustering framework, negative-free and weight-decorrelated contrastive network（NFWD）, is proposed. First, a feature graph is constructed as a supplementary view by node attribute similarity. Node representations from the feature graph and the original graph are obtained via Laplacian smoothing filters and a shared-parameter multilayer perceptron, respectively. Consequently, the reliance of the original graph on the homophily assumption is significantly reduced. Second, to tackle the false negative problem caused by class conflicts in heterophilous graphs, cluster information is derived from adaptively fused node representations for the construction of cluster-central node representations. Then, a negative-free strategy combining node-level and cluster-level feature contrast is proposed to effectively mitigate this problem. Finally, an orthogonal constraint is applied to the weight matrix of MLP to actively suppress redundant features. Experiments on six benchmark graph datasets demonstrate the effectiveness and robustness of NFWD in graph-agnostic scenarios.
[1] LIN Z P, KANG Z, ZHANG L Z, et al. Multi-view Attributed Graph Clustering. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(2): 1872-1880. [2] XIE F, ZHANG Z, LI L, et al. EpiGNN: Exploring Spatial Transmission with Graph Neural Network for Regional Epidemic Forecasting//Proc of the European Conference on Machine Learning and Knowledge Discovery in Databases. Berlin, Germany: Springer, 2023: 469-485. [3] GROVER A, LESKOVEC J. node2vec: Scalable Feature Learning for Networks//Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2016: 855-864. [4] COSCIA M, GIANNOTTI F, PEDRESCHI D.A Classification for Community Discovery Methods in Complex Networks. Statistical Analysis and Data Mining, 2011, 4(5): 512-546. [5] WANG S P, YANG J B, YAO J, et al. An Overview of Advanced Deep Graph Node Clustering. IEEE Transactions on Computational Social Systems, 2024, 11(1): 1302-1314. [6] 周丽娟,吴梦琪,李欣冉,等.基于不同学习范式的深度图聚类方法综述.模式识别与人工智能, 2025, 38(3): 233-251. (ZHOU L J, WU M Q, LI X R, et al. A Survey of Deep Graph Clustering Methods Based on Different Learning Paradigms. Pattern Recognition and Artificial Intelligence, 2025, 38(3): 233-251.) [7] YING R, HE R N, CHEN K F, et al. Graph Convolutional Neural Networks for Web-Scale Recommender Systems//Proc of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2018: 974-983. [8] 方宝富,张旭,王浩. 联合深度图聚类与目标检测的像素级分割算法. 模式识别与人工智能. 2022, 35(2): 130-140. (FANG B F, ZHANG X, WANG H.Pixel-Level Segmentation Algorithm Combining Depth Map Clustering and Object Detection. Pa-ttern Recognition and Artificial Intelligence, 2022, 35(2): 130-140.) [9] SHCHUR O, GÜNNEMANN S. Overlapping Community Detection with Graph Neural Networks[C/OL].[2025-08-21]. https://arxiv.org/pdf/1909.12201. [10] PAN S R, HU R Q, LONG G D, et al. Adversarially Regularized Graph Autoencoder for Graph Embedding//Proc of the 27th International Joint Conference on Artificial Intelligence. San Francisco, USA: IJCAI, 2018: 2609-2615. [11] KIPF T N, WELLING M.Variational Graph Auto-Encoders[C/OL].[2025-08-21].https://arxiv.org/pdf/1611.07308. [12] GOODFELLOW I, POUGET-ABADIE J, MIRZA M, et al. Gene-rative Adversarial Networks. Communications of the ACM, 2020, 63(11): 139-144. [13] HASSANI K, AHMADI A H K. Contrastive Multi-view Representation Learning on Graphs//Proc of the 37th International Confe-rence on Machine Learning. San Diego, USA: JMLR, 2020: 4116-4126. [14] YANG X H, LIU Y, ZHOU S H, et al. Cluster-Guided Contrastive Graph Clustering Network. Proc of the AAAI Conference on Artificial Intelligence, 2023, 37(9): 10834-10842. [15] GONG L, ZHOU S H, TU W X, et al. Attributed Graph Clustering with Dual Redundancy Reduction//Proc of the 31st International Joint Conference on Artificial Intelligence. San Francisco,USA: IJCAI, 2022: 3015-3021. [16] WANG C, PAN S R, HU R Q, et al. Attributed Graph Clustering: A Deep Attentional Embedding Approach//Proc of the 28th International Joint Conference on Artificial Intelligence. San Francisco, USA: IJCAI, 2019: 3670-3676. [17] TU W X, ZHOU S H, LIU X W, et al. Deep Fusion Clustering Network. Proceedings of the AAAI Conference on Artificial Intelligence, 2021, 35(11): 9978-9987. [18] XIA J, WU L R, WANG G, et al. ProGCL: Rethinking Hard Negative Mining in Graph Contrastive Learning//Proc of the 39th International Conference on Machine Learning. San Diego, USA: JMLR, 2022: 24332-24346. [19] LIU Y, XIA J, ZHOU S H, et al. A Survey of Deep Graph Clustering: Taxonomy, Challenge, and Application[C/OL].[2025-08-21]. https://arxiv.org/pdf/2211.12875. [20] LIU Y, ZHOU S H, YANG X H, et al. Improved Dual Correlation Reduction Network with Affinity Recovery. IEEE Transactions on Neural Networks and Learning Systems, 2025, 36(4): 6159-6173. [21] XIA W, WANG Q Q, GAO Q X, et al. Self-Consistent Contrastive Attributed Graph Clustering with Pseudo-Label Prompt. IEEE Tran-sactions on Multimedia, 2023, 25: 6665-6677. [22] LIU Y, YANG X H, ZHOU S H, et al. Simple Contrastive Graph Clustering. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(10): 13789-13800. [23] CHEN J L, KOU G.Attribute and Structure Preserving Graph Contrastive Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 2023, 37(6): 7024-7032. [24] ZHENG Y M, JIA C Y, YU J.Attributed Graph Clustering under the Contrastive Mechanism with Cluster-Preserving Augmentation. Information Sciences, 2024, 681. DOI: 10.1016/j.ins.2024.121225. [25] ZHAO H, YANG X, WANG Z R, et al. Graph Debiased Contrastive Learning with Joint Representation Clustering//Proc of the 30th International Joint Conference on Artificial Intelligence. San Francisco, USA: IJCAI, 2021: 3434-3440. [26] ZBONTAR J, JING L, MISRA I, et al. Barlow Twins: Self-Supervised Learning via Redundancy Reduction//Proc of the 38th International Conference on Machine Learning. San Diego, USA: JMLR, 2021: 12310-12320. [27] ZHANG H R, WU Q T, YAN J C, et al. From Canonical Correlation Analysis to Self-Supervised Graph Neural Networks//Proc of the 35th International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2021: 76-89. [28] MO Y H, WANG X, FAN S H, et al. Graph Contrastive Invariant Learning from the Causal Perspective. Proceedings of the AAAI Conference on Artificial Intelligence, 2024, 38(8): 8904-8912. [29] FANG R Y, WEN L J, KANG Z, et al. Structure-Preserving Graph Representation Learning//Proc of the IEEE International Confe-rence on Data Mining. Washington, USA: IEEE, 2022: 927-932. [30] HUA T Y, WANG W X, XUE Z H, et al. On Feature Decorrelation in Self-Supervised Learning//Proc of the IEEE/CVF International Conference on Computer Vision. Washington, USA: IEEE, 2021: 9578-9588. [31] LI S, JIA K, WEN Y X, et al. Orthogonal Deep Neural Networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 43(4): 1352-1368. [32] BANSAL N, CHEN X H, WANG Z Y.Can We Gain More from Orthogonality Regularizations in Training Deep CNNs?//Proc of the 32nd International Conference on Neural Information Processing Systems. Cambridge, USA: MIT Press, 2018: 4266-4276. [33] CUI G Q, ZHOU J, YANG C, et al. Adaptive Graph Encoder for Attributed Graph Embedding//Proc of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2020: 976-985. [34] PEI H B, WEI B Z, CHANG K C C, et al. Geom-GCN: Geome-tric Graph Convolutional Networks[C/OL].[2025-08-21]. https://arxiv.org/pdf/2002.05287. [35] CHEN J F, ZHU G H, QI Y F, et al. Towards Self-Supervised Learning on Graphs with Heterophily//Proc of the 31st ACM International Conference on Information and Knowledge Management. New York, USA: ACM, 2022: 201-211. [36] KINGMA D P, BA J.Adam: A Method for Stochastic Optimization[C/OL].[2025-08-21]. https://arxiv.org/pdf/1412.6980. [37] BERGSTRA J, YAMINS D, COX D.Making a Science of Model Search: Hyperparameter Optimization in Hundreds of Dimensions for Vision Architectures//Proc of the 30th International Confe-rence on Machine Learning. San Diego, USA: JMLR, 2013: 115-123. [38] BO D Y, WANG X, SHI C, et al. Structural Deep Clustering Network//Proc of the ACM Web Conference. New York, USA: ACM, 2020: 1400-1410. [39] LIU Y, YANG X H, ZHOU S H, et al. Hard Sample Aware Network for Contrastive Deep Graph Clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 2023, 37(7): 8914-8922. [40] GU M, YANG G M, ZHOU S, et al. Homophily-Enhanced Struc-ture Learning for Graph Clustering//Proc of the 32nd ACM International Conference on Information and Knowledge Management. New York, USA: ACM, 2023: 577-586. [41] VAN DER MAATEN L, HINTON G. Visualizing Data Using t-SNE. Journal of Machine Learning Research, 2008, 9(86): 2579-2605.
2025, Vol. 38 
